1. Field of the Invention
The present invention relates generally to point cloud data, and in particular, to a method, apparatus, and article of manufacture for automatically segmenting point cloud data from an urban environment into objects.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by references enclosed in brackets e.g., [x]. Such references may indicate the first named authors and year of publication e.g., [Jones 2002]. A list of these different publications ordered according to these references can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
Laser scanner equipment is increasingly employed for surveying and urban planning, etc. The data acquired by ground-based laser scanners is extensive and dense. Further, the data (referred to as point-cloud data) is difficult to interpret especially when no color or intensity information is available. Segmentation is a critical pre-processing step in the interpretation of the scanned environment. In this regard, segmentation refers to the operation that separates points into different groups based on spatial characteristics without knowing what the groups really are. Segmentation is used to identify the object shape and then extract the shape descriptors. Segmentation results in a semantic description of the environment that can be used to support high-level decisions. Moreover, the quality of a classification of an object can also be improved based on segmentation results. To better understand segmentation, a description of the prior art and related work may be useful.
When a laser scanner is used to scan a scene/urban environment, the scene often contains many objects. It is difficult to determine which points belong to which objects in the scene. For example, if a city block is laser scanned, in addition to an office building, there may be many objects such as trees, vegetation, roads, etc. It is desirable to pick out which points belong to the building and which points belong to the vegetation, to the ground, and to other roads. Segmentation is performed to separate the points into various groups/objects in order to classify the points. Various methods have been attempted in the prior art to quickly and efficiently segment laser-scanned data. However, most of the prior art techniques are problematic with large ground based complex streets/scenes.
The topic of point cloud segmentation has been researched for several years. In some scenarios, segmentation is performed on a point cloud scanned from a single object and the goal is to decompose the point cloud into separate surface patches. Embodiments of the present invention only focus on the related works of segmentation of point clouds from an urban environment. Urban environments are usually very complex and consist of many objects. Further, the surfaces of the objects are not smooth and it is difficult to estimate the differential geometric properties. In view of such properties, it can be seen that other segmentation methods are quite different from the surface patch segmentation of point clouds.
Some researchers segment three-dimensional (3D) laser point cloud based on a graph cut method such as a normalized cut and minimum (min) cut [Boykov 2006]. Aleksey et al. [Alkeskey 2009] segmented the foreground points from the background points by a min cut method on a 3D graph built on a nearest neighbor graph. Such a method requires prior knowledge of the location of the objects to be segmented. Zhu et. al [Zhu 2010] also proposed a graph-based segmentation of range images in an urban environment. However, Zhu's method requires the removal of ground points beforehand.
Another category of segmentation approaches (other than the graph-based segmentation) are focused on the explicit modeling of surface discontinuity. Melkumyan [Melkumyan 2008] first built a 3D mesh from the point cloud data and then defined the discontinuity based on the long edge and acute angle of the mesh. However, the mesh reconstruction of laser scanning data from an outdoor environment is not trivial in itself. Moonsmann [Moonsmann 2009] segments ground and objects from 3D LiDAR (light detection and ranging) scans based on local convexity measures. Although such a method is fast and may show good results in some kind of urban environments, it is not general enough to handle the cases with overhanging structures.
Segmentation approaches based on statistics are also explored by Hernandez and Marcotegui [Hernandez 2009]. The 3D points are projected to a horizontal plane. The number of points projected to the same cell is accumulated to form an accumulated image and the maximal height in each cell is extracted to form a range image. However, this method assumes that the principal objects in the scene are facade buildings and that the ground data is perpendicular to facade data. Accordingly, such an approach is not general for other environments.
In view of the above, what is needed is the ability to segment point cloud data of an urban environment scene in order to remove extraneous objects and separate the point cloud data into individual objects for further processing.